/*
  Grupo 2
  
  Luiz Felipe de Souza Mattos 	RA 107822
  
  Debora Maia Silva 	      	RA 101985

*/

#include <stdio.h>
#include <stdlib.h>
#include "heap.h"

/* aloca um novo no e inicializa as informacoes */
Arvore * InsereNo(int freq,unsigned char carac,Arvore *esq,Arvore *dir,Arvore *pai)
{
	Arvore *inicio;

	inicio = (Arvore *)malloc(sizeof(Arvore));

	inicio->info.freq = freq;
	inicio->info.carac = carac;
	inicio->esq = esq;
	inicio->dir = dir;
	inicio->pai = pai;

	return inicio;
}

/* libera a memoria usada pela arvore */
void LiberaArvore(Arvore **p)
{
	if (*p == NULL)
		return;
	LiberaArvore(&(*p)->esq);
	LiberaArvore(&(*p)->dir);
	free(*p);
	*p = NULL;
	p = NULL;
}

/* insere em uma lista ligada, na posicao crescente de frequencia e de acordo com o 
indice do caractere na tabela ASC para frequencias iguais */
void InsereLista(ListaSimples **inicio,Info info,Arvore *pont)
{
	ListaSimples * aux,*novo;

	aux = *inicio;

	novo = (ListaSimples *)malloc(sizeof(ListaSimples));

	novo->freq = info.freq;
	if ((int)info.carac >= 0)
		novo->carac = info.carac;
	else
		novo->carac = 256 + (int)info.carac;
	novo->no = pont;

	/* caso a lista esteja vazia */
	if (aux == NULL)
	{
		/* atualiza o inicio da lista */
		novo->prox = NULL;
		*inicio = novo;
		return;
	}
	/* caso nao esteja vazia */
	else
	{
		/* caso o novo registro fique antes do primeiro da lista */
		if (aux->freq > info.freq)
		{
			/* atualiza os ponteiros e o inicio da lista */
			novo->prox = aux;
			*inicio = novo;
			return;
		}
		/* caso o novo registro tenha frequencia igual ao primeiro registro
		da lista e tenha que ser colocado antes do primeiro registro */
		if (aux->freq == info.freq)
		{
			if (aux->carac > info.carac)
			{
				/* atualiza ponteiros e o inicio da lista */
				novo->prox = aux;
				*inicio = novo;
				return;
			}
		}
		/* caso tenha que percorrer a lista para achar a posicao */
		if (aux->freq <= info.freq)
		{
			/* percorre a lista procurando a frequencia certa */
			while (aux->prox != NULL && aux->prox->freq < info.freq)
			{
					aux = aux->prox;
			}
			/* percorre a lista procurando o indice na tabela ASC correto caso
			as frequencias sejam iguais */
			while (aux->prox != NULL && aux->prox->freq == info.freq && aux->prox->carac < info.carac)
			{
					aux = aux->prox;
			}

			/* atualiza os ponteiros */
			novo->prox = aux->prox;
			aux->prox = novo;
		}
	}
}

/* recebe como entrada a lista ordenada, retira e retorna o elemento
de maior prioridade */
ListaSimples * TiraLista(ListaSimples **inicio)
{
	ListaSimples * aux;

	aux = *inicio;
	*inicio = aux->prox;
	return aux;
}

/* recebe como entrada a lista ordenada, retira e retorna o primeiro registro */
Lista * TiraLista2(Lista **inicio)
{
	Lista * aux;

	if (*inicio == NULL)
		return NULL;

	aux = *inicio;
	*inicio = aux->prox;
	return aux;
}

/* monta a lista ordenada a partir do vetor do heap */
ListaSimples * MontaLista(Heap *p)
{
	int i = 0;
	ListaSimples *inicio = NULL;
	Arvore *no;

	while (p->vet[i].freq != 0 && i < p->tam)
	{
		no = InsereNo(p->vet[i].freq,p->vet[i].carac,NULL,NULL,NULL);
		InsereLista(&inicio,p->vet[i],no);
		i++;
	}

	return inicio;
}

/* usa o algoritmo de montar a arvore de Huffman para montar a arvore corretamente */
Arvore * MontaArvore(ListaSimples **lista)
{
	ListaSimples *aux;
	Arvore *raiz1,*raiz2,*raiz;
	unsigned char carac;

	/* enquanto tiver elementos na lista ordenada */
	while (*lista != NULL)
	{
		/* retira o elemento de maior prioridade */
		aux = TiraLista(lista);
		raiz1 = aux->no;
		free(aux);
		/* retira o elemento de maior prioridade */
		aux = TiraLista(lista);
		raiz2 = aux->no;
		free(aux);
		
		if (raiz1->info.carac < raiz2->info.carac)
			carac = raiz1->info.carac;
		else
			carac = raiz2->info.carac;

		/* aloca o novo no pai dos registros retirados e inicializa as informacoes */
		raiz = InsereNo(raiz1->info.freq + raiz2->info.freq,carac,raiz1,raiz2,NULL);

		/* atualiza os pais dos registros */
		raiz1->pai = raiz;
		raiz2->pai = raiz;

		/* caso ainda tenha registros na lista ordenada */
		if (*lista != NULL)
			/* insere o pai criado na lista */
			InsereLista(lista,raiz->info,raiz);
	}

	return raiz;
}

/* insere na lista ligada, cada passo do caminho da raiz ate o caractere */
void InsereLista2(Lista **inicio,int valor)
{
	Lista *novo;

	novo = (Lista *)malloc(sizeof(Lista));
	
	novo->valor = valor;
	novo->prox = *inicio;

	*inicio = novo;
}

/* imprime o caminho da raiz ate o caractere */
void ImprimeLista(Lista *lista)
{
	Lista *aux;

	aux = lista;
	while (aux != NULL)
	{
		printf("%d",aux->valor);
		aux = aux->prox;
	}
	printf("\n");
}

/* imprime sem o \n para o codificar */
void ImprimeListaCod(Lista *lista)
{
	Lista *aux;

	aux = lista;
	while (aux != NULL)
	{
		printf("%d",aux->valor);
		aux = aux->prox;
	}
}

/* libera a memoria usada pela lista do caminho da raiz ate o caractere */
void LiberaLista(Lista **lista)
{
	Lista *aux;

	aux = *lista;

	while (aux != NULL)
	{
		*lista = aux->prox;
		free(aux);
		aux = NULL;
		aux = *lista;
	}
}

/* libera a memoria usada por uma lista ligada do tipo ListaSimples */
void LiberaListaSimples(ListaSimples **lista)
{
	ListaSimples *aux;

	aux = *lista;

	while (aux != NULL)
	{
		*lista = aux->prox;
		free(aux);
		aux = NULL;
		aux = *lista;
	}

	*lista = NULL;
}

/* acha recursivamente o caminho da raiz ate o no passado como parametro */
void AchaCaminho(Arvore *reg,Lista **lista, int cod)
{
	if (reg->pai != NULL)
 	{
		/* se for filho da esquerda, insere um 0 no inicio da lista */
  		if (reg->pai->esq == reg)
   			InsereLista2(lista,0);
		/* se for filho da direita, insere um 1 no inicio da lista */
  		if (reg->pai->dir == reg)
   			InsereLista2(lista,1);
		/* chama a funcao para o pai */
  		AchaCaminho(reg->pai,lista, cod);
 	}
 	else
 	{
		if(!cod)
			ImprimeLista(*lista);
		
		else ImprimeListaCod(*lista);
		
  		LiberaLista(lista);
		*lista = NULL;
  		return;
 	}
 	return;
}

/* acha recursivamente o caminho da raiz ate o no passado como parametro e 
nao limpa a lista ligada auxiliar, nem imprime */
void AchaCaminho2(Arvore *reg,Lista **lista,int modo)
{
	Lista *aux,**aux2;

	/* move o ponteiro para o final da lista caso seja a compactacao */
	if (modo == 1)
	{
		aux = *lista;

		if (*lista != NULL)
		{
			while(aux->prox != NULL)
				aux = aux->prox;

			aux2 = &aux->prox;
		}
		else
			aux2 = lista;
	}
	else
		/* caso nao seja a compactacao ou seja uma chamada recursiva, inicializa o ponteiro */
		aux2 = lista;

	/* insere um registro no inicio da lista passada como parametro */
	if (reg->pai != NULL)
 	{
		/* se for filho da esquerda, insere um 0 no inicio da lista */
  		if (reg->pai->esq == reg)
   			InsereLista2(aux2,0);
		/* se for filho da direita, insere um 1 no inicio da lista */
  		if (reg->pai->dir == reg)
   			InsereLista2(aux2,1);
		/* chama a funcao para o pai */
  		AchaCaminho2(reg->pai,aux2,0);
 	}

 	return;
}

/* converte decimal em binario e retorna a lista ligada */
void dec2bin(int decimal,Lista **lista)
{
     int i;
     int n = 0;
     
     for (i = 0;i < 8;i++)
     {
         InsereLista2(lista,decimal % 2);
         decimal = decimal / 2;
         n++;
     }
     
	return;
}

/* segue a codificacao em texto ou binario e imprime a traducao para
texto */
void SegueCaminho(FILE * entrada,Arvore *raiz)
{
	int n,i = 0;
	unsigned char aux;
	Arvore *p;
	Lista *lista = NULL,*atual;

	/* le o numero de bytes */
	fscanf(entrada,"%d\n",&n);
	/* le o tipo de descompressao (texto ou binario)*/
	fscanf(entrada,"%c\n",&aux);
	p = raiz;
	if (aux == 'T')
	{
		/* le a codificacao em texto e vai descendo na arvore ate encontrar uma folha,
		ao chegar na folha, imprime o caractere correspondente e volta para a raiz da arvore */
		while (!feof(entrada))
		{
			fscanf(entrada,"%c",&aux);
			if (aux == '0')
			{
				p = p->esq;
			}
			else if (aux == '1')
			{
				p = p->dir;
			}
			if (p->dir == NULL && p->esq == NULL)
			{
				printf("%c",p->info.carac);
				p = raiz;
			}
		}
	}
	else if (aux == 'B')
	{
		/* le a codificacao em texto e vai descendo na arvore ate encontrar uma folha,
		ao chegar na folha, imprime o caractere correspondente e volta para a raiz da arvore */
		while (i < n)
		{
			atual = TiraLista2(&lista);

			if (p == NULL)
				p = raiz;
			if (atual == NULL)
			{
				fscanf(entrada,"%c",&aux);
				/* converte de decimal (indice na tabela ASCII) para binario */
				dec2bin((int)aux,&lista);
				atual = TiraLista2(&lista);
			}

			if (atual->valor == 0)
			{
				p = p->esq;
			}
			else if (atual->valor == 1)
			{
				p = p->dir;
			}
			free(atual);
			if (p->dir == NULL && p->esq == NULL)
			{
				printf("%c",p->info.carac);
				p = raiz;
				i++;
			}
		}
		LiberaLista(&lista);
	}
}

/* reconstroi a arvore de acordo com o caminho de cada caractere na codificacao
do arquivo do tipo huff */
Arvore * ReconstroiArv(FILE * entrada)
{
	int n,i,k;
	unsigned char carac,aux;
	Arvore *raiz = NULL,*p,*f;

	fscanf(entrada,"%d\n",&n);

	if (raiz == NULL && n > 0)
		raiz = InsereNo(0,0,NULL,NULL,NULL);

	p = raiz;

	for (i = 0;i < n;i++)
	{
		fscanf(entrada,"%d ",&k);
		carac = (unsigned char)k;

		p = raiz;
		while (!feof(entrada))
		{
			fscanf(entrada,"%c",&aux);
			if (aux == '\n')
			{
				p->info.carac = carac;
				break;
			}
			if (aux == '0')
			{
				if (p->esq == NULL)
				{
					f = InsereNo(0,0,NULL,NULL,p);
					p->esq = f;
					p = f;
				}
				else
					p = p->esq;
			}
			else if (aux == '1')
			{
				if (p->dir == NULL)
				{
					f = InsereNo(0,0,NULL,NULL,p);
					p->dir = f;
					p = f;
				}
				else
					p = p->dir;
			}
			
		}
	}
	
	return raiz;
}
